package main

import "fmt"

// // 堆排序-算法导论版本
// type HeapSortAlgorithms struct {
// 	Value []int
// }

// func (s *HeapSortAlgorithms) Sort() ([]int, error) {
// 	s.buildMaxHeap()
// 	for i := len(s.Value) - 1; i > 0; i-- {
// 		s.Value[i], s.Value[0] = s.Value[0], s.Value[i]
// 		s.maxHeapify(0, i)
// 	}
// 	return s.Value, nil
// }

// func (s *HeapSortAlgorithms) maxHeapify(t, len int) {
// 	if t >= len {
// 		return
// 	}
// 	largest, left, right := t, Left(t), Right(t)

// 	if left < len && s.Value[left] > s.Value[largest] {
// 		largest = left
// 	}

// 	if right < len && s.Value[right] > s.Value[largest] {
// 		largest = right
// 	}

// 	if largest != t {
// 		s.Value[t], s.Value[largest] = s.Value[largest], s.Value[t]
// 		s.maxHeapify(largest, len)
// 	}
// }

// func (s *HeapSortAlgorithms) buildMaxHeap() {
// 	for i := len(s.Value)/2 - 1; i >= 0; i-- {
// 		s.maxHeapify(i, len(s.Value))
// 	}
// }

// func Left(t int) int {
// 	return 2*t + 1
// }

// func Right(t int) int {
// 	return 2*t + 2
// }

func heapSort(value []int) ([]int, error) {
	buildMaxHeap(value)
	for i := len(value) - 1; i > 0; i-- {
		value[i], value[0] = value[0], value[i]
		maxHeapify(value, 0, i)
	}
	return value, nil
}

func maxHeapify(value []int, t, len int) {
	if t >= len {
		return
	}
	largest, left, right := t, Left(t), Right(t)

	if left < len && value[left] > value[largest] {
		largest = left
	}

	if right < len && value[right] > value[largest] {
		largest = right
	}

	if largest != t {
		value[t], value[largest] = value[largest], value[t]
		maxHeapify(value, largest, len)
	}
}

func buildMaxHeap(value []int) {
	for i := len(value)/2 - 1; i >= 0; i-- {
		maxHeapify(value, i, len(value))
	}
}

func Left(t int) int {
	return 2*t + 1
}

func Right(t int) int {
	return 2*t + 2
}

func main() {
	fmt.Printf("quickSort start\n")

	arrInit := []int{3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9, 3, 2, 3, 8, 4, 6, 2, 6, 4, 3, 3, 8, 3, 2, 7, 9, 5, 0, 2, 8, 8}
	fmt.Printf("arrInit:%v\n", arrInit)

	arrSorted, _ := heapSort(arrInit)
	fmt.Printf("arrSorted:%v\n", arrSorted)
}
